Internet Info 1994 March/Internet Info CD-ROM (Walnut Creek) (March 1994).iso/answers/rec/puzzles/archive/induction

Text File | 1993-08-17 | 16KB | 416 lines

Newsgroups: rec.puzzles,news.answers,rec.answers
Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
From: [e-mail] (Chris Cole)
Subject: rec.puzzles Archive (induction), part 16 of 35
Message-ID: <puzzles/archive/[e-mail]>
Followup-To: rec.puzzles
Summary: This is part of an archive of questions
 and answers that may be of interest to
 puzzle enthusiasts.
 Part 1 contains the index to the archive.
 Read the rec.puzzles FAQ for more information.
Sender: [e-mail] (Chris Cole)
Reply-To: [e-mail]
Organization: Questrel, Inc.
References: <puzzles/archive/[e-mail]>
Date: Wed, 18 Aug 1993 06:05:34 GMT
Approved: [e-mail]
Expires: Thu, 1 Sep 1994 06:04:11 GMT
Lines: 394
Xref: senator-bedfellow.mit.edu rec.puzzles:24998 news.answers:11518 rec.answers:1918

Archive-name: puzzles/archive/induction
Last-modified: 17 Aug 1993
Version: 4


==> induction/handshake.p <==
A married couple organizes a party. They only invite other married
couples. At least one person of an invited couple is acquainted to
at least the host or the hostess (so between sets {host,hostess} and
{male of invited couple, female of invited couple} there exists at
least one relation, but two, three or four relations is also possible).
Upon arrival at the party, each person shakes hands with all other
guests he/she doesn't know yet (it is assumed everybody knows
him/herself and his/her partner).

When all couples have arrived and all the handshaking has been done,
the host mingles between the guests and ask everybody (including his
wife): "How many hands did you shake?". To his surprise, all responses
are different.

With the above information, you must be able to determine how many
hands the host and hostess each shook.

==> induction/handshake.s <==
Assume there were 2n people (including host and hostess)
in the party.

1. When the host asked the question he must have got
   2n-1 responses (including from his wife).

2. All of the responses were different.

The responses have to be (0, 1, 2, 3, ..., 2n-2)
to satisfy the above requirements. As 2n-2 is the maximum
possible handshakes any person in this party could have made.

/**   Below,
      P{x} - means a person who shook x hands.
      H    - means the host
 **/

H: <-------->2n-2   0
       2n-3        1
          2n-4          2
      2n-5          3
          .             .
           .           .
             .       .
          n  n-1 n-2

        (There are 2n-1 on the circle.)

P{2n-2} must have handshaked with H (because in the circle he
can handshake with only 2n-3. He has to exclude himself also.)

P{2n-3} must have handshaked with H (because in the circle he
can handshake with only 2n-4.)

P{2n-4} must have handshaked with H (because in the circle he
can handshake with only 2n-5.)

P{n} must have handshaked with H (because in the circle he
can handshake with only n-1.)

from P{n-1} to P{0} nobody  handshakes with H, because, for them
the handshake numbers are satisfied on the circle itself.

This leaves H with (n-1) handshakes.
----------------------------------

P{0} must be the spouse of P{2n-2} (since P{2n-2} handshakes with
everbody else.)
.
.
.
same logic till P{n-2}

leaving the Hostess to be P{n-1}.

----------------------------------------
So,
Host    - made (n-1) handshakes.
Hostess - made (n-1) handshakes.

where n is the number of couple including
the host couple.
----------------------------------------

==> induction/hanoi.p <==
Is there an algorithm for solving the Hanoi tower puzzle for any number
of towers?  Is there an equation for determining the minimum number of
moves required to solve it, given a variable number of disks and towers?

==> induction/hanoi.s <==
The best way of thinking of the Towers of Hanoi problem is inductively.
To move n disks from post 1 to post 2, first move (n-1) disks
from post 1 to post 3, then move disk n from post 1 to post 2, then move
(n-1) disks from post 3 to post 2 (same procedure as moving (n-1) disks
from post 1 to post 3).  In order to figure out how to move (n-1) disks
from post 1 to post 3, first move (n-2) disks . . . .

As far as an algorithm which straightens out any legal position is
concerned, the algorithm would go something like this:

1.  Find the smallest disk.  Call the post that it's on post 1.

2.  Find the smallest disk which is not on post 1.  This disk is, say,
size k.  (I am calling the smallest disk size 1 here.)  Call the post
that disk k is on post 2.  Disks 1 through (k-1) are then all stacked up
correctly on post 1 disk k is on top of post 2.  This follow from the
fact that the disks are in a legal postition.

3.  Move disks 1 through (k-1) from post 1 to post 2, ignoring the other
disks.  This is just the standard Tower of Hanoi problem for (k-1)
disks.

4.  If the disks are not yet correctly arranged, repeat from step 1.

In fact, this gives the straightening with the fewest number of moves.

With 3 towers, for N number of disks, the formula for the minimum number of
moves to complete the puzzle correctly is:
        (2^N) - 1

This bit of ancient folklore was invented by De Parville in 1884.

``In the great temple at Benares, says he, beneath the dome which
  marks the centre of the world, rests a brass plate in which are
  fixed three diamond needles, each a cubit high and as thick as
  the body of a bee.  On one of these needles, at the creation,
  God placed sixty-four discs of pure gold, the largest disc resting
  on the brass plate, and the others getting smaller and smaller
  up to the top one.  This is the Tower of Bramah.  Day and night
  unceasingly the priests transfer the discs from one diamond needle
  to another according to the fixed and immutable laws of Bramah,
  which require that the priest on duty must not move more than one
  disc at a time and that he must place this disc on a needle so
  that there is no smaller disc below it.  When the sixty-four
  discs shall have been thus transferred from the needle on which
  at the creation God placed them to one of the other needles,
  tower, temple, and Brahmins alike will crumble into dust, and
  with a thunderclap the world will vanish.''  (W W R Ball,
  MATHEMATICAL RECREATIONS AND ESSAYS, p. 304)

This has been discussed by several authors, e.g.

    Er, Info Sci 42 (1987) 137-141.
    Graham, Knuth and Patashnik, _Concrete_Mathematics_.

There are many papers claiming to solve this, and they are probably
all correct but they rely on the unproven "Frame's conjecture".
In particular, for the 4 peg case the conjecture states that an optimal
solution begins by forming a substack of the k smallest discs, then moving
the rest, and then moving those k again; k to be determined.

Here is a extensible bc program that does the same work. The output
format is not that great. We get 300 numbers as output. The first
hundred represent N, the next 100 represent f(N) and the last hundred
represent i, which is the number of discs to move to tmp1 using f(N).
For convenience, I have here some values for N <= 48. Enjoy.

Sharma


N     1   2   3  4  5   6  7  8  9  10  11 12 13  14  15  16  17  18  19
f(N)     1   3   5  9 13  17 25 33 41  49  65 81 97 113 129 161 193 225 257
i     0   1   1  2  2   3  3  4  5   6   6  7  8   9  10  10  11  12  13


N    20   21  22  23  24  25  26  27  28  29  30   31   32   33   34   35
f(N)    289 321 385 449 513 577 641 705 769 897 1025 1153 1281 1409 1537 1665
i    14   15  15  16  17  18  19  20  21  21   22   23   24   25   26   27

N    36    37    38    39     40    41   42   43   44   45   46   47   48
f(N)    1793 2049  2305  2561   2817  3073 3329 3585 3841 4097 4609 5121 5633
i    28    28    29    30     31    32    33   34   35   36  36   37   38


/* This is the bc program that gives f(N) for 4 peg case */

w = 101; /* This represents the number of disks */

m[0] = 0;
m[1] = 1;
m[2] = 3;
m[3] = 5;
m[4] = 9;
m[5] = 13;
m[6] = 17;

/* f(n) is the function that gives the min # of moves for 4 peg case */
define f(n) {
  return (m[n]);
}

/* g(n) is the function that fives the min # of moves for 3 peg case */
define g(n) {
  return (2^n - 1);
}

/* x(n) is the Optimization Routine */

define x(n) {
  auto j
  auto r
  auto i

  if(n == 1) return (1);
  j = f(1) + g(n-1);

  for(i = 2; i < n; i++) {
    r = f(i) + g(n-i);
    if(r < j) { j = r; d = i; }
  }
  return (j);
}

/* main program */
for(q = 4; q < w; q++) {
  t = x(q-1);
  m[q] = 2 * t + 1;
  d[q] = d;
};


/*This for loop prints the number of discs from 1 <= n <=  w*/

for(q = 1; q < w; q++) {
q;
}

/*This for loop prints f(n) for 1 <= n <= w */

for(q = 1; q < w; q++) {
m[q];
}

/*This for loop prints i for 1 <= n <= w
i represents the number of disks to be moved to tmp location using f(n)
N-i-1 will be moved using g(n) */

for(q = 1; q < w; q++) {
d[q];
}

--
[e-mail]

There is a solution to the Tower of Hanoi problem which does not require
recursion.  On odd-numbered moves, move the smallest sized disk clockwise.
On even-numbered moves, make the single other move which is possible.

==> induction/n-sphere.p <==
With what odds do three random points on an n-sphere form an acute triangle?

==> induction/n-sphere.s <==
Select three points a, b, and c, randomly with respect to the surface of an
n-sphere.  These three points determine a fourth, x, which is the intersection
of the sphere with the axis perpendicular to the abc plane.  (Choose the pole
nearest the plane.) I could have, just as easily, selected x, a distance d
from x, and three points d units away from x.  The distribution of d is not
uniform, but that's ok.  For every x and d, the three points abc form an acute
triangle with probability p[n-1].  By induction, p[n] = 1/4.

==> induction/paradox.p <==
Is there a non-trivial property that holds for the first 10,000 positive
integers, then fails?

==> induction/paradox.s <==
Consider the sequences defined by:
s(1) = a; s(2) = b; s(n) = least integer such that s(n)/s(n-1) > s(n-1)/s(n-2).
In other words, s(n) = 1+floor(s(n-1)^2/s(n-2)) for n >= 3.  These
sequences are similar in some ways to the classically-studied Pisot
sequences.  For example, if a = 1, b = 2, then we get the odd-indexed
Fibonacci numbers.

D. Boyd of UBC, an expert in Pisot sequences, pointed out the following.
If we let a = 8, b = 55 in the definition above, then the resulting
sequence s(n) appears to satisfy the following linear recurrence
of order 4:

    s(n) = 6s(n-1) + 7s(n-2) - 5s(n-3) - 6s(n-4)

Indeed, it does satisfy this linear recurrence for the
first 11,056 terms.  However, it fails at the 11,057th term!
And s(11057) is a 9270 digit number.
(The reason for this coincidence depends on a remarkable fact
about the absolute values of the roots of the polynomial
x^4 - 6x^3 - 7x^2 + 5x + 6.)

==> induction/party.p <==
You're at a party.  Any two (different) people at the party have exactly one
friend in common (the friend is also at the party).  Prove that there is at
least one person at the party who is a friend of everyone else.  Assume that
the friendship relation is symmetric and not reflexive.

==> induction/party.s <==
Here is an easy solution by induction. Let P be the set of people in the
party, and n the size of P. If n=2 or 3, the result is trivial. Suppose now
that n>3 and that the result is true for n-1.

For any two distinct x,y in P, write x & y to mean that `x is a friend of y',
and x ~& y to mean that `x is not a friend of y'.

Take q in P. The hypothesis on the relation & is still satisfied on P-{q}; by
induction, the result is thus true for P-{q}, and there is some p in P-{q}
such that p & x for any x in P-{p,q}. We have two cases:

a) p & q. Then the result holds for P with p.

b) p ~& q. By hypothesis, there is a unique r in P-{p,q} such that p & r & q.
For any x in P-{p,q}, if x & q, then p & x & q, and so x=r. Thus r is the
unique friend of q. Now for any s in P-{q,r} there exists some x such that s &
x & q, and so x=r. This means that r & s for any s in P-{q,r}, and as r & q,
the results holds in P with r.

The problem can also be solved by applying the spectral theory of graphs
(see for instance Bollobas' excellent book, _Extremal Graph Theory_).

The problem's condition is vacuous if there is only N=1 person at the "party",
impossible if N=2 (If you aren't your own friend, nor I mine, somebody *else*
must be our mutual friend), and trivial if N=3 (everybody must be everyone
else's friend).  Henceforth assume N>3.

Let A,B be two friends, and C their mutual friend.  Let a be the number
of A's friends other than B and C, and likewise b,c.  Each of A's friends
is also friendly with exactly one other of A's friends, and with none of
B and C's other friends (if A1,B1 are friends of A,B resp. and of each other
then A1 and B have more than one mutual friend); likewise for B and C.
Let M=N-(a+b+c+3) be the number of people not friendly with any of A,B,C.
Each of them is friendly with exactly one of A's and one of B's friends;
and each pair of a friend of A and a friend of B must have exactly
one of them as a mutual friend.  Thus M=ab; likewise M=ab=ac=bc. Thus
either M and two of a,b,c vanish, or a=b=c=k (say), M=k^2, and N=k^3+3k+3.
In the first case, say b=c=0; necessarily a is even, and A is a friend of
everybody else at the party, each of whom is friendly with exactly one other
person; clearly any such configuration (a graph of k/2+1 triangles with a
common vertex) satisfies the problem's conditions).

It remains to show that the second case is impossible.  Since N=k^2+3k+3
does not depend on A,B,C, neither does k, and it quickly follows that the
party's friendship graph is regular with reduced matrix

         [  0   k+2   0  ]
         [  1    1    k  ]
         [  0    1   k+1 ]

and eigenvalues k+2 and +-sqrt(k+1) and multiplicities 1,m1,m2 for some
*integers* m1 and m2 such that (m1-m2)*sqrt(k+1)=-(k+2) (because the graph's
matrix has trace zero).  Thus sqrt(k+1) divides k+2 and k+1 divides

        (k+2)^2=(k+1)(k+3)+1

which is only possible if k=0,  Q.E.D.

==> induction/roll.p <==
An ordinary die is thrown until the running total of the throws first
exceeds 12.  What is the most likely final total that will be obtained?

==> induction/roll.s <==
Claim: If you throw a die until the running total exceeds n>=5, a final
outcome of n+1 is more likely than any other.

Assume we throw an m for a total n+k>n+1, and assume m-k>=0.  Now, it
is just as likely to throw an m as an m-k+1, which means that the sum
n+1 is just as likely as any other.  Now consider the series of throws
consisting of n-5 1's followed by a 6 and note that we cannot achieve
more than an n+1 by changing the last die roll.  Hence, a total of n+1
is more likely than any other.

==> induction/takeover.p <==
After graduating from college, you have taken an important managing position
in the prestigious financial firm of "Mary and Lee".
You are responsible for all the decisions concerning take-over bids.
Your immediate concern is whether to take over "Financial Data".
There is no doubt that you will be successful if you are the first to
bid and that this will be profitable for the firm and you in the long
run.  However, you know that there exist another n financial firms,
similar to "Mary and Lee", that are also considering the possibility.
Although you are likely to be the first one to move, you know that
just after a take-over there is a lot of adjustment that needs to be
done.  In fact, for a period of time following any take-over the
successful firm becomes a prime candidate for a take-over which will
cost the job of whoever is responsible for take-overs.  Among all
financial firms it is common knowledge that the managers responsible
for take-overs are rational and intelligent.  What is your best response?

==> induction/takeover.s <==
Assume the takeover is wise for n.  The takeover is then unwise for
n+1, as the other companies now find themselves in the same situation
as you for n.  If the decision is unwise for n, by similar reasoning
it is wise to takeover FD for n+1.  Now note that for n=1 the takeover
decision is clearly unwise, hence by induction you should takeover
FD iff n is even.